//
//  TreeDepth.swift
//  AlgorithmOne
//
//  Created by 刘彬彬 on 2020/3/10.
//  Copyright © 2020 LBB. All rights reserved.
//  解题思路，每个结点的左右子树遍历相加，再比较每个结点这个相加值的大小，最大就是最大路径

import Foundation

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int,_ left: TreeNode!,_ right: TreeNode!) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Tree {
    var maxLenght = 0
    //确认是否根节点
    var point = Unmanaged<AnyObject>.passUnretained(AnyObject.self as AnyObject).toOpaque()
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        if (root == nil) {
            return 0
        }
        //根节点的内存地址
        point = Unmanaged<AnyObject>.passUnretained(root as AnyObject).toOpaque()
        depth(root!)
        return maxLenght
    }
    
    func depth(_ root:TreeNode) -> Int {
        if (root.left == nil && root.right == nil) {
            return 1
        }
        //正在访问节点的内存地址
        let rootTreePoint = Unmanaged<AnyObject>.passUnretained(root as AnyObject).toOpaque()
        var left = 0
        var right = 0
        //除根结点外，只要左右子树有其一，那么边 = 1，否则 = 0
        if (root.left != nil) {
            left = depth(root.left!)
        } else {
            //特殊情况，根节点是否有左子树，没有深度则为0，其他子树节点没有深度则为1
            left = (rootTreePoint == point) ? 0 : 1
        }
        if (root.right != nil) {
            right = depth(root.right!)
        } else {
            //特殊情况，根节点是否有右子树，没有深度则为0，其他子树节点没有深度则为1
            right = (rootTreePoint == point) ? 0 : 1
        }
        //计算根节点左子树+右子树的深度,在取较大边数的结点
        maxLenght = max(left + right, maxLenght);
        let add = (left == 0 || right == 0) ? 0 : 1
        return max(left, right) + add
    }
    
    //两值取大
    func max(_ a:Int,_ b:Int) -> Int {
        return a > b ? a : b
    }
}


